﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarTtree.Codec
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            //TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
            TreeNode treeNode = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
            Codec codec = new Codec();
            TreeNode treeNode1 = codec.deserialize(codec.serialize(treeNode));
            Console.ReadKey();
        }

        /// <summary>
        /// BFS
        /// </summary>
        public class Codec
        {

            // Encodes a tree to a single string.
            public string serialize(TreeNode root)
            {
                if (root == null) return string.Empty;
                string str = string.Empty;
                Queue<TreeNode> que = new Queue<TreeNode>();
                que.Enqueue(root);
                str += root.val /*+ "#"*/;
                while (que.Count > 0)
                {
                    int size = que.Count;
                    for (int i = 0; i < size; i++)
                    {
                        TreeNode treeNode = que.Dequeue();
                        if (treeNode.left != null) { que.Enqueue(treeNode.left); str += ","+treeNode.left.val; }
                        else str += ",-1001";
                        if (treeNode.right != null) { que.Enqueue(treeNode.right); str += "," + treeNode.right.val; }
                        else str += ",-1001";
                    }
                    //str += "#";
                }
                Console.WriteLine("serialize = " + str);
                return str;
            }


            // Decodes your encoded data to tree.
            public TreeNode deserialize(string data)
            {
                if (data.Equals(string.Empty)) return null;
                Queue<TreeNode> que = new Queue<TreeNode>();
                string[] allData = data.Split(',');
                TreeNode root = new TreeNode(int.Parse(allData[0]));
                que.Enqueue(root);
                int index = 1;
                while (que.Count > 0)
                {
                    int size = que.Count;
                    for (int i = 0; i < size; i++)
                    {
                        TreeNode treeNode = que.Dequeue();
                        if (allData[index]!="-1001")
                        {
                            treeNode.left = new TreeNode(int.Parse(allData[index]));
                            que.Enqueue(treeNode.left);
                        }
                        else
                        {

                        }
                        index++;
                        if (allData[index] != "-1001")
                        {
                            treeNode.right = new TreeNode(int.Parse(allData[index]));
                            que.Enqueue(treeNode.right);
                        }
                        else
                        {

                        }
                        index++;
                    }
                }
                return root;
            }
        }
    }
}
